package com.cn.codebrush.动态规划;

/**
 * @Author Boolean
 * @Date 2022/5/11 22:27
 * @Version 1.0
 */
public class No1646获取生成数组中的最大值 {
    public static void main(String[] args) {
        int n =100;
        System.out.println(getMaximumGenerated(n));
    }

    public static int getMaximumGenerated(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            if(i%2 == 0){
                dp[i] = dp[i/2];
            }else {
                dp[i] = dp[i/2] + dp[i/2+1];
            }
        }
        int res = dp[0];
        for(int j=0;j<=n;j++){
            res = Math.max(res,dp[j]);
        }

        return res;
    }
}
